package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.ListNode;

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 */
public class P51 {

    /**
     * 解决方案
     *
     * 1. 假定 链表A长度: a+n 链表B长度:b+n, 且 a<b
     * 2. 定义指针cur1指向链表A头结点headA，指针cur2指向链表B头结点headB
     * 3. 同时遍历链表A、B，那么cur1会先到链表尾部，此时，cur2走到 a+n处
     * 4.
     *
     *
     * 那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部
     * 接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。
     * 将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。 或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。 同理a>=b.
     */
    public class Solution {
        public ListNode<Integer> getIntersectionNode(ListNode<Integer> headA, ListNode<Integer> headB) {
            ListNode<Integer> cur1 = headA;
            ListNode<Integer> cur2 = headB;
            while (cur1 != cur2) {
                cur1 = cur1 == null ? headB : cur1.next;
                cur2 = cur2 == null ? headA : cur2.next;
            }
            return cur1;
        }
    }
}
